package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/jump-game-ii/
 * 使用最少步数
 * LC45_2
 * see LC55
 *
 * @author tzp
 * @since 2020/10/17
 */
public class LC45 implements Greedy {
    public int jump(int[] nums) {
        if (nums.length <= 1) return 0;
        int[] minSteps = new int[nums.length];
        for (int i = nums.length - 2; i >= 0; i--) {//从数组后面倒着来; LC45_2才是更适合的贪心思路, 从左往右
            if (nums[i] + i >= nums.length - 1) {
                minSteps[i] = 1;
            } else {
                int minStep = Integer.MAX_VALUE;
                for (int j = nums[i]; j >= 1; j--) {
                    minStep = Math.min(minStep, minSteps[i + j]);
                }
                minSteps[i] = minStep == Integer.MAX_VALUE ? Integer.MAX_VALUE : 1 + minStep;
            }
        }
        System.out.println(Arrays.toString(minSteps));
        return minSteps[0];
    }

    public static void main(String[] args) {
        System.out.println(new LC45().jump(new int[]{2, 3, 1, 1, 4}));
        System.out.println(new LC45().jump(new int[]{2, 2, 1, 2, 4}));
        System.out.println(new LC45().jump(new int[]{2, 2, 1, 0, 4}));
    }
}
